package com.company.heap;

import java.nio.BufferUnderflowException;

/**
 * Created by v on 16-12-8.
 */
public class BinomialQueue<E extends Comparable<E>> {
    private static final int DEFAULT_TREES=4;

    private int size;
    private Node<E> [] theTrees=new Node[DEFAULT_TREES];

    public BinomialQueue(){
        size=0;
    }

    public BinomialQueue(E e){
        theTrees[0]=new Node<E>(e);
        size=1;
    }

    public void merge(BinomialQueue<E> rhs){
        if(this==rhs){
            return;
        }

        size+=rhs.size;
        if(size>capacity()){
            Node<E>[] temp=new
                    Node[Math.max(theTrees.length,rhs.theTrees.length)+1];
            for(int i=0;i<theTrees.length;i++){
                temp[i]=theTrees[i];
            }
            theTrees=temp;
        }

        Node<E> carry=null;
        for(int i=0,j=1;j<=size;i++,j*=2){
            int whichCase=0;
            whichCase+=theTrees[i]==null? 0:1;
            if(i<rhs.theTrees.length){
                whichCase+=rhs.theTrees[i]==null?0:2;
            }
            whichCase+=carry==null?0:4;

            switch (whichCase){
                case 0:
                case 1: break;

                case 2: theTrees[i]=rhs.theTrees[i]; break;

                case 4:
                    theTrees[i]=carry;
                    carry=null;
                    break;

                case 3:
                    carry=merge(theTrees[i],rhs.theTrees[i]);
                    theTrees[i]=null;
                    break;

                case 5:
                    carry=merge(theTrees[i],carry);
                    theTrees[i]=null;
                    break;

                case 6:
                    carry=merge(rhs.theTrees[i],carry);
                    break;

                case 7:
                    Node<E> temp=theTrees[i];
                    theTrees[i]=carry;
                    carry=merge(rhs.theTrees[i],temp); break;
            }
        }

        rhs.clear();
    }

    public void add(E e){
        merge(new BinomialQueue<E>(e));
    }

    public E poll(){
        if(isEmpty())
            throw new BufferUnderflowException();

        size--;
        int minIndex=findMinIndex();
        E minElement=theTrees[minIndex].element;

        //在数组中把根值最小的那棵树删除
        Node<E> current=theTrees[minIndex].Child;
        theTrees[minIndex]=null;

        BinomialQueue<E> deleteTree=new BinomialQueue<E>();
        deleteTree.expandTheTree(minIndex);
        for(int i=minIndex-1;i>=0;i--){
            deleteTree.theTrees[i]=current;
            current=current.nextSibling;
            deleteTree.theTrees[i].nextSibling=null;
        }

        merge(deleteTree);

        return minElement;
    }

    public E peek(){
        return theTrees[findMinIndex()].element;
    }

    private static class Node<E extends Comparable<E>>{
        private E element;
        private Node<E> Child;
        private Node<E> nextSibling;

        private Node(E element){
            this.element=element;
        }
    }

    /**
     * 创建一颗空的树，poll之后的重组操作
     * @param newNumberTree　空树的数组大小
     */
    private void expandTheTree(int newNumberTree){
        theTrees=new Node[newNumberTree];
    }

    private int capacity(){
        return (1<<theTrees.length)-1;
    }

    private int findMinIndex(){
        int minIndex=-1;
        int i=0;
        E minElement=null;
        for(;i<theTrees.length;i++){
            if(theTrees[i]!=null){
                minElement=theTrees[i].element;
                minIndex=i;
                break;
            }
        }

        for(;i<theTrees.length;i++){
            if(theTrees[i]!=null
                    &&minElement.compareTo(theTrees[i].element)>0){
                minElement=theTrees[i].element;
                minIndex=i;
            }
        }

        return minIndex;
    }

    private Node<E> merge(Node<E> t1,Node<E> t2){
        if(t1.element.compareTo(t2.element)>0){
            return merge(t2,t1);
        }

        t2.nextSibling=t1.Child;
        t1.Child=t2;
        return t1;
    }

    public void clear(){
        size=0;
        theTrees=new Node[4];
    }

    public boolean isEmpty(){
        return size==0;
    }
}